// https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

// 算法思路总结：
// 1. 归并排序过程中统计逆序对数量
// 2. 合并时当左元素大于右元素时累加逆序对
// 3. 逆序对数量为左半部分剩余元素个数
// 4. 分治保证每个逆序对只被统计一次
// 5. 时间复杂度：O(n log n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int reversePairs(vector<int>& record) 
    {
        int ret = 0;
        mergesort(record, 0, record.size() - 1, &ret);

        return ret;
    }

    void mergesort(vector<int>& record, int left, int right, int* ret)
    {
        if (left >= right)
        {
            return ;
        }

        int mid = (left + right) >> 1;
        mergesort(record, left, mid, ret);
        mergesort(record, mid + 1, right, ret);

        vector<int> tmp(right - left + 1);
        int cur1 = left, cur2 = mid + 1, index = 0;

        while (cur1 <= mid && cur2 <= right)
        {
            if (record[cur1] <= record[cur2])
            {
                tmp[index++] = record[cur1++];
            }
            else
            {
                *ret += mid - cur1 + 1;
                tmp[index++] = record[cur2++];
            }
        }

        while (cur1 <= mid)
        {
            tmp[index++] = record[cur1++];        
        }

        while (cur2 <= right)
        {
            tmp[index++] = record[cur2++];
        }

        for (int i = left ; i <= right ; i++)
        {
            record[i] = tmp[i - left];
        }
    }
};

int main()
{
    vector<int> record = {9, 7, 5, 4, 6};
    Solution sol;

    cout << sol.reversePairs(record) << endl;

    return 0;
}